'''
@Descripttion: 
@version: 
@encoding: utf-8
@Author: qiurongcan
Date: 2025-09-08 09:43:07
LastEditTime: 2025-09-08 10:54:54
'''
# 分割子集

# 0 - 1背包问题
# 将target看作背包容量，每个nums[i]是物品的价值和重量
# 定义dp[i][j]表示将前i个物品装入背包时，背包的容量为j时的最佳组合
# 外层物体循环，内层容量循环

class Solution:

    def canPartition(self, nums):
        total_sum = sum(nums)
        # 和为奇数
        if total_sum % 2 != 0:
            return False

        target = total_sum // 2
        # 一共有多少个物体
        n = len(nums)

        # 创建背包
        dp = [[False] * (target + 1) for _ in range(n + 1)]
        # print(dp)
        for i in range(n + 1):
            dp[i][0] = True
        # 相当于每个物体都用来装一下
        for i in range(0, n):
            # print(nums[i])
            for j in range(1, target + 1):
                # 包的容量太小，装不下，此时的价值与 i - 1个时相同的
                if j < nums[i]:
                    dp[i][j] = dp[i-1][j]
                
                else:
                    # 先把当前物体装入，剩下的空间考虑给前面 i - 1个物体
                    dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]]
            
            # 优化，提前结束
            if dp[i][target]:
                return dp[i][target]
        
        return dp[n - 1][target]



if __name__ == "__main__":
    nums = [1, 17, 11, 5]

    sol = Solution()
    res = sol.canPartition(nums)
    print(res)




